package com.ssh;

public class MergeKLists_23 {
	public class ListNode {
		int val;
		ListNode next;
		ListNode(int x) { val = x; }
	}
	public ListNode mergeKLists(ListNode[] lists) {
		int n = lists.length;
		if (n == 0) {
			return null;
		}
		return p(lists, 0, n-1);
    }
	private ListNode p(ListNode[] lists, int s, int e) {
		if (s == e) {
			return lists[s];
		}else if (s < e) {
			int mid = (e - s) / 2 + s;
			ListNode l = p(lists, s, mid);
			ListNode r = p(lists, mid + 1, e);
			return m(l, r);
		}else {
			return null;
		}
	}
	private ListNode m(ListNode x, ListNode y) {
		ListNode s = new ListNode(0);
		ListNode z = s;
		while (x != null || y != null) {
			if (x == null) {
				s.next = y;
                y = (y == null || y.next == null) ? null : y.next;
			}else if (y == null) {
				s.next = x;
                x = (x == null || x.next == null) ? null : x.next;
			}else if (x.val < y.val) {
				s.next = x;
                x = (x == null || x.next == null) ? null : x.next;
			}else {
				s.next = y;
                y = (y == null || y.next == null) ? null : y.next;
			}
            s = s.next;
		}
		return z.next;
	}
}
